/*
 * CKYParser.java
 *
 * Created on June 29, 2006, 2:32 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package galronnlp.pcfg.parser;

import galronnlp.util.Grammar;
import galronnlp.util.Tuple;
import galronnlp.util.Tree;
import galronnlp.util.SymbolGenerator;
import galronnlp.util.Symbol;
import galronnlp.util.SortedLinkedList;

import galronnlp.pcfg.unpacker.ParseFinder;
import galronnlp.pcfg.unpacker.Unpacker;

import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.File;

import java.util.LinkedList;
import java.util.Iterator;

import java.lang.Integer;

/**
 *
 * @author Dan
 */
public class CKYParser {
    boolean TRACE = false;
    String grammarFile;
    String lexiconFile;
    String inputSentence;
    Symbol StartSymbol;
    int chartType;
    int N;
    double beam;
           
    
    Grammar grammar;
    Chart chart;
    SymbolGenerator gen = new SymbolGenerator();
    
    CKYParser(String grammarFile, String lexiconFile, String inputSentence, String StartSymbol, int ChartType, boolean trace, double beam) {
        this.grammarFile = grammarFile;
        this.lexiconFile = lexiconFile;
        this.inputSentence = inputSentence;
        this.StartSymbol = gen.create(StartSymbol);
        this.chartType = ChartType;
        this.TRACE = trace;
        this.beam = beam;
        grammar = new Grammar(grammarFile, lexiconFile, this.StartSymbol, gen);
        chart = new Chart(chartType, trace);
    }

    CKYParser(String grammarFile, String lexiconFile, String inputSentence, String StartSymbol, int ChartType, boolean trace, int N) {
        this.grammarFile = grammarFile;
        this.lexiconFile = lexiconFile;
        this.inputSentence = inputSentence;
        this.StartSymbol = gen.create(StartSymbol);
        this.chartType = ChartType;
        this.TRACE = trace;
        this.N = N;
        grammar = new Grammar(grammarFile, lexiconFile, this.StartSymbol, gen);
        chart = new Chart(chartType, trace);        
    }

    CKYParser(Grammar g, String inputSentence, String StartSymbol, int ChartType, boolean trace, double beam, SymbolGenerator gen) {
        this.gen = gen;
        this.inputSentence = inputSentence;
        this.StartSymbol = gen.create(StartSymbol);
        this.chartType = ChartType;
        this.TRACE = trace;
        this.beam = beam;
        grammar = g;
        chart = new Chart(chartType, trace);
    }    
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        String inputSentenceFile = args[2];
        String ss                = args[3];
        String type              = args[4];
        String trace             = args[5];
        String stringN           = args[6];
        String stringBeam        = args[7];
        
        double beam = 1 - (new Double(stringBeam)).doubleValue();
        
        SymbolGenerator sg = new SymbolGenerator();
        Grammar g = new Grammar(args[0], args[1], sg.create(ss), sg);
        System.out.println(g);
        int N = (new Integer(stringN)).intValue();
        int chartType = Chart.ALL;
        if(type.equalsIgnoreCase("all")) {
            chartType = Chart.ALL;
        } else if(type.equalsIgnoreCase("best")) {
            chartType = Chart.BEST;
        } else {
            System.err.println("Unknown option: assuming ALL");
        }
        
        boolean t = false;
        if(trace.equalsIgnoreCase("trace")) {
            t = true;
        }
        String is = "";
        try {
            BufferedReader reader = new BufferedReader(new FileReader(new File(inputSentenceFile)));
            is = reader.readLine();
        } catch(IOException e) {
            e.printStackTrace();
        }

        CKYParser parser = new CKYParser(g, is, ss, chartType, t, beam, sg);
        //System.out.println(parser.parse());
        //System.exit(1);
        if(parser.parse()) {

            ParseFinder pf = new ParseFinder(parser.chart, 0, parser.inputSentence.split(" ").length, parser.StartSymbol);
            
            System.out.println(pf.getBestParse());
            System.out.println(parser.grammar.score(pf.getBestParse()));
            //System.exit(1);
            SortedLinkedList<Tuple> parses = pf.getBestParses(beam);
            LinkedList<Tree> trees = new LinkedList<Tree>();
            System.out.println("---------!!!--------------");
            while(parses.size() > 0) {
                Tree tree = (Tree)parses.removeHighest().get(1);
                System.out.println(g.score(tree));
                trees.addLast(tree);
            }
            System.out.println("---------!!!--------------");            
            for(Iterator<Tree> i = trees.iterator(); i.hasNext();) {
//                System.out.println(i.next());
            }
            //System.out.println(parses.size());
        }
        
    }

    /**
     * Parse the sentence without using the agenda
     */
    public boolean parse() {
        String[] input = inputSentence.split(" ");
        System.out.println(inputSentence);
        // Find Unary rule closure and replace the unary rules as defined in the grammar
        // with their closure
        //UnaryClosure closure = new UnaryClosure(this.grammar);
        //this.grammar.unaryRules = closure.getUnaryClosure();
        //System.out.println("######");
        //System.out.println(grammar);        
        // Initialize the chart with lexical items; that is, put the correct lexical
        // entry for each word in the input sentence, which corresponds to span
        // (i, i+1) in the chart.
        for(int i = 0; i < input.length; i++) {
            // Get all possible lexical entries for the word at position i in the
            // input sentence
            LinkedList<Tuple> tlist = grammar.lexicon.get(gen.create(input[i]));
            // Put each lexical item found for word i into the chart
            for(Iterator<Tuple> it = tlist.iterator(); it.hasNext(); ) {
                Tuple lextup = it.next();
                chart.add(i, i+1, (Symbol)lextup.get(0), new EntryTriple((Double)lextup.get(1), new Integer(1), new LexicalEdge(gen.create(input[i]))));
            }
        }
        // Iterate through all possible span lengths
        for(int spanlength = 1; spanlength <= input.length; spanlength++) {
            // iterate through all chart entries
            for(int begin = 0; begin < input.length - spanlength + 1; begin++) {
                // Define the end of the span in terms of the begin and the span length
                int end = begin + spanlength;
                // Expand all Unary rules which are in the chart at (begin, end)
                LinkedList<Tuple> unary = chart.expandUnary(grammar, begin, end);
                // Iterate through all binary expansions of the chart at (begin, end), and add
                // them to the chart as well.
                for(Iterator<Tuple> i = unary.iterator(); i.hasNext(); ) {
                    Tuple tuple4 = i.next();
                    chart.add(begin, end, (Symbol)tuple4.get(0), new EntryTriple((Double)tuple4.get(2), (Integer)tuple4.get(3), new UnaryEdge((Symbol)tuple4.get(1))));
                }
                // Iterate through all possible divisions of the span (begin, end)
                // into (begin, mid) and (mid, end)
                for(int m = begin; m < end; m++) {
                    // For each possible Binary expansion, where the left non-terminal
                    // of the LHS spans (begin, mid) and where the  right non-terminal
                    // of the LHS spans (mid, end)
                    LinkedList<Tuple> binary = chart.expandBinary(grammar, begin, m, end);
                    // Add each binary expansion found to (begin, end)
                    for(Iterator<Tuple> i = binary.iterator(); i.hasNext(); ) {
                        Tuple tuple5 = i.next();
                        chart.add(begin, end, (Symbol)tuple5.get(0), new EntryTriple((Double)tuple5.get(3), (Integer)tuple5.get(4), new BinaryEdge(m, (Symbol)tuple5.get(1), (Symbol)tuple5.get(2))));
                    }
                }
                if(TRACE)
                    System.out.println("(" + begin + ", " + end + ")");
            }
        }
        if(TRACE) {
            System.out.println(chart);
            System.out.println(chart.size());
        }
        // Returns True iff the start symbol is found spanning the entire sentence.
        return chart.hasFinalEntry(0, input.length, StartSymbol);
    }

    /**
     * Parse the sentence using the agenda to guide rule expansion. Basically, instead
     * of expanding rules and putting them directly in the chart, push the expanded
     * rules onto the Agenda, and at the end of each iteration, put the expansions into
     * the chart.
     */    
    public boolean agendaParse() {
        Agenda agenda = new Agenda();
        String[] input = inputSentence.split(" ");
        System.out.println(inputSentence);
        // Iterate through the sentence, and get all lexical rules for each word
        // in teh sentence, and push them on the agenda
        for(int i = 0; i < input.length; i++) {
            LinkedList<Tuple> tlist = grammar.lexicon.get(gen.create(input[i]));
            for(Iterator<Tuple> it = tlist.iterator(); it.hasNext(); ) {
                Tuple lextup = it.next();
                agenda.push(i, i+1, (Symbol)lextup.get(0), new EntryTriple((Double)lextup.get(1), new Integer(1), new LexicalEdge(gen.create(input[i]))));
            }
        }
        // empty the agenda into the chart
        while(agenda.size() > 0) {
            AgendaEntry entry = agenda.pop();
            chart.add(((Integer)entry.get(0)).intValue(), ((Integer)entry.get(1)).intValue(), (Symbol)entry.get(2), (EntryTriple)entry.get(3));
        }
        // Iterate through all possible span lengths
        for(int spanlength = 1; spanlength <= input.length; spanlength++) {
            // iterate through all chart entries
            for(int begin = 0; begin < input.length - spanlength + 1; begin++) {
                int end = begin + spanlength;
                // Expand all Unary rules which are in the chart at (begin, end)
                LinkedList<Tuple> unary = chart.expandUnary(grammar, begin, end);
                // Iterate through all Unary rules found and push them on the agenda
                for(Iterator<Tuple> i = unary.iterator(); i.hasNext(); ) {
                    Tuple tuple4 = i.next();
                    agenda.push(begin, end, (Symbol)tuple4.get(0), new EntryTriple((Double)tuple4.get(2), (Integer)tuple4.get(3), new UnaryEdge((Symbol)tuple4.get(1))));
                }
                // Iterate through all possible divisions of the span (begin, end)
                // into (begin, mid) and (mid, end)
                for(int m = begin; m < end; m++) {
                    // For each possible Binary expansion, where the left non-terminal
                    // of the LHS spans (begin, mid) and where the  right non-terminal
                    // of the LHS spans (mid, end)
                    LinkedList<Tuple> binary = chart.expandBinary(grammar, begin, m, end);
                    // Add each binary expansion found to the agenda
                    for(Iterator<Tuple> i = binary.iterator(); i.hasNext(); ) {
                        Tuple tuple5 = i.next();
                        agenda.push(begin, end, (Symbol)tuple5.get(0), new EntryTriple((Double)tuple5.get(3), (Integer)tuple5.get(4), new BinaryEdge(m, (Symbol)tuple5.get(1), (Symbol)tuple5.get(2))));
                    }
                }
            }
            // Empty the agenda onto the chart
            while(agenda.size() > 0) {
                AgendaEntry entry = agenda.pop();
                chart.add(((Integer)entry.get(0)).intValue(), ((Integer)entry.get(1)).intValue(), (Symbol)entry.get(2), (EntryTriple)entry.get(3));
            }            
        }        
        
        if(TRACE) {
            System.out.println(chart);
            System.out.println(chart.size());
        }
        return chart.hasFinalEntry(0, input.length, StartSymbol);
    }

    
}
